package com.ruyuan2020.im.code;

public class LongestPalindrome {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }

        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i); // Odd length palindromes
            int len2 = expandAroundCenter(s, i, i + 1); // Even length palindromes
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }


    private int expandAroundCenter(String s,int left,int right){
        while (left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
        return right-left-1;
    }

    public static void main(String[] args) {
        LongestPalindrome solution = new LongestPalindrome();
        String s1 = "babad";
        String s2 = "cbbd";
        System.out.println("Longest palindromic substring of " + s1 + " is: " + solution.longestPalindrome(s1));
        System.out.println("Longest palindromic substring of " + s2 + " is: " + solution.longestPalindrome(s2));
    }
}
